Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Raga sono di nuovo qui e la cosa non è positiva Oggi sono alle prese con queste tracce:
-Realizzare una funzione ricorsiva che ricerca un elemento x in un array ordinato di interi.
-Scrivere una funzione ricorsiva che controlla se una parola è palindroma, ovvero se “rigirandola” non cambia.
La seconda traccia non l'ho ancora neanche provata a svolgere e quindi per il momento non chiedo nulla, perchè spero di saperla fare dopo aver risolto i problemi con la prima.
Ora, io ho capito il funzionamento di una funzione ricorsiva, e ho capito che devo cercare prima di tutto un "passo base"; solo che nel mio caso non riesco a trovarlo. Posto il codice che ho scritto fino e ora, ma è incompleto per il motivo che vi ho detto
Codice sorgente - presumibilmente C++
//Rierca valore in array tramite ricorsiva
#include <iostream>
usingnamespace std;
#define N 8
typedefint vettore[N];
vettore vett;
int posizione;
int ricerca(vettore,int a);
int main(){
int input,posizione;
for(int i=0;i<N;i++){
cout<<"Inserire un valore nell'array : ";
cin>> vett[i];
}
cout<<"Inserire l'elemento da cercare : ";
cin>>input;
posizione = ricerca(vett,input);
}
int ricerca(vettore,int a){
}
Non sto chiedendo di scrivermi il codice, ma qualche suggerimento su come impostare la funzione ricorsiva sarebbe possibile?
N.B :Per il momento non sto considerando l'array ordinato, ne ho semplicemente inserito uno generico.
Ultima modifica effettuata da cos.peluso il 07/01/2018 alle 17:23
La funzione ricorsiva, è una funzione che richiama se stessa
Esempio di Array Ordinato:
0
1
2
3
4
5
6
7
8
9
Per cercare un numero, la soluzione più semplice sarebbe confrontare il numero cercato con tutti gli elementi dell array finchè non trovi quello che cerchi. Sapendo che l'array è ordinato (in modo crescente ad esempio) puo confrontarli finchè il numero cercato è minore del numero con cui effettui il confronto.
Se il numero cercato è 0, al primo confronto lo trovi, se è 9 , ci voranno 10 confronti.
Ad esempio cerchiamo il numero 8 (chiamiamolo X) , e vediamo (ragionando senza scrivere codice per ora).
Un metodo che potresti utilizzare è quello di dividere l'array in 2 parti, dal 0-4 e dal 5-9 .
Se X < di 4 (che è il limite del primo blocco) sarà sicuramente nel 1° blocco, se maggiore sicuramente nel 2° .
Esssendo magiore , sarà nel2° blocco (5-9).
Ora ripetiamo il ragionamento e dividiamo il blocco in altre 2 parti (5-7 e 8-9). Ragianando come prima vedrai che X sta nel "nuovo" 2° blocco (8-9).
Di nuovo ripetiamo il ragionamento. dividendo il blocco in 2 parti. (8 e 9). Con il confronto avrai trovato il tuo elemento.
Questo è un ragionamento possibile per sfongere la tua funzione. Ora se hai capito il meccanismo, prova ad implementarlo tu.
Siccome l'array è ordinato puoi usare il binary search come dice Mikelius; una alternativa nel caso non lo fosse sarebbe quella di dividere l'array in due parti: una la testa (head) che sarebbe il primo elemento, e l'altra la coda (tail) che rappresenta tutti gli altri elementi.
Se l'elemento da cercare è la testa, allora ritorni la posizione, altrimenti richiami ricorsivamente la funzione sulla coda.
Siccome creare nuovi array da passare alla funzione ricorsiva di base diventa macchinoso, ti conviene aggiungere un parametro che indichi la posizione da cui parte l'array considerato nella funzione ricorsiva (al caso base, 0).
Se invece adotti la soluzione di mikelius ti serviranno due parametri in più, che indicano la posizione iniziale e finale del pezzo di array che consideri (caso base 0 e lunghezza, cioè estremo finale escluso).
Ultima modifica effettuata da lumo il 07/01/2018 alle 17:58
int ricerca(int v[],int start,int end,int search);
int main(){
int input,posizione;
int vett[8]={1,2,3,4,5,6,7,8};
cout<<"Inserire l'elemento da cercare : ";
cin>>input;
posizione = ricerca(vett,0,N-1,input);
cout<<"La posizione e' : "<<posizione<<endl;
}
int ricerca(int v[],int start,int end,int search){
int med;
med=(start +(end-start))/2;
if(v[med]==search)
{
return med;
}
else
if(v[med]<search){
return ricerca(v,med+1,end,search);
}
else
if(v[med]>search){
return ricerca(v,start,med-1,search);
}
}
Ho ancora ancora dei dubbi, il processo credo di averlo scritto più o meno bene, però , come faccio a inserire nella funzione ricorsiva anche il caso in cui il valore cercato non sia presente ?
Inoltre per alcuni valori che inserisco, mi dice che il nomefile.exe ha smesso di funzionare , è un problema del mio computer o fa sempre parte di un errore nel mio codice ?
Ultima modifica effettuata da cos.peluso il 08/01/2018 alle 12:31
ho provato il tuo codice, funziona per alcuni numeri, mentre inserendo un 6 pare che vada in loop generando l'errore.
Se la richiesta non specifica algoritmi più complessi fossi in te per semplicità di scrittura proseguirei con una ricerca sequenziale.
Cercando ovviamente di strutturare il codice in maniera più leggibile.
qua verrà end/2, che non va bene. Ti serve (start+end)/2 (provare qualche esempio per credere)
Codice sorgente - presumibilmente C/C++
return ricerca(v,start,med-1,search);
Togli il -1 perché l'estremo superiore è incluso (altrimenti bisogna rimaneggiare le formule).
Per coerenza
Codice sorgente - presumibilmente Plain Text
posizione = ricerca(vett,0,N-1,input);
metti 0, N.
Il crash lo hai perché quando l'elemento non viene trovato, la ricerca va avanti fuori dagli indici consentiti, e questo causa un segmentation fault (il sistema operativo si accorge che accedi ad aree di memoria non allocate dal tuo programma).
Devi mettere un controllo all'inizio della funzione che controlla questo fatto e in tal caso termina la ricorsione ritornando la posizione.
Ultima modifica effettuata da lumo il 08/01/2018 alle 21:11
Ok raga, grazie agli spunti presi da un po tutte le vostre risposte sono riuscito a scrivere un codice funzionante , appena vado a casa dove ho il Wi-Fi copio il codice e ve lo mostro, così vedo se ci sono cose inutili o errori che non riesco a vedere .
Ultima modifica effettuata da cos.peluso il 09/01/2018 alle 16:37
int ricerca(int v[],int start,int end,int search);
int main(){
int input,posizione;
int vett[8]={1,2,3,4,5,6,7,8};
cout<<"Inserire l'elemento da cercare : ";
cin>>input;
if(input<=0 || input>8){
cout<<"Nessun valore corrispondente."<<endl;}
else{
posizione = ricerca(vett,0,N,input);
cout<<"La posizione e' : "<<posizione+1<<endl;}
system("PAUSE");
return0;
}
int ricerca(int v[],int start,int end,int search){
int med;
med=(start + end)/2;
if(v[med]==search)
{
return med;
}
else
if(v[med]<search){
return ricerca(v,med,end,search);
}
else
if(v[med]>search){
return ricerca(v,start,med,search);
}
}
Questo è il codice scritto e funziona bene.L'unico dubbio che ho ancora è, come potevo includere il caso del non esistente all'interno della funzione ricorsiva? Includendo un passo base ancora?
![C/C++ - Ricerca in array con funzione ricorsiva [C++]](/data/logos/logositov9.png)
| 
